import operator

from 第三章.stack import Stack
from 节点与引用实现二叉树 import BinaryTree


def build_parse_tree(exp: str) -> BinaryTree:
    exp_list = exp.split()
    exp_stack = Stack()
    exp_tree = BinaryTree('')

    exp_stack.push(exp_tree)
    current_tree = exp_tree

    for i in exp_list:
        if i == '(':
            current_tree.insert_left('')
            exp_stack.push(current_tree)
            current_tree = current_tree.get_left_child()

        elif i not in '+-*/)':
            current_tree.set_root_obj(eval(i))
            parent = exp_stack.pop()
            current_tree = parent

        elif i in '+-*/':
            current_tree.set_root_obj(i)
            current_tree.insert_right('')
            exp_stack.push(current_tree)
            current_tree = current_tree.get_right_child()

        elif i == ')':
            current_tree = exp_stack.pop()

        else:
            raise ValueError('Unknown Operator')

    return exp_tree


def evaluate(exp_tree: BinaryTree) -> int:
    opers = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}

    left_c = exp_tree.get_left_child()
    right_c = exp_tree.get_right_child()

    if left_c and right_c:
        fn = opers[exp_tree.get_root_value()]
        return fn(evaluate(left_c), evaluate(right_c))

    else:
        return exp_tree.get_root_value()


if __name__ == '__main__':
    exp_str = '( 1 + 2 ) * ( 3  + 4 )'
    exp_tree = build_parse_tree(exp_str)
    result = evaluate(exp_tree)
    print(result)